#include <iostream>
#include <unordered_map>
using namespace std;
using ll = long long;

constexpr inline static ll mod = 1e9+7;

constexpr inline static ll fpow(ll base, ll exp, ll m) {
    base %= m;
    ll res = 1;
    while (exp) {
        if (exp & 1) res = (res * base) % m;
        base = (base * base) % m;
        exp >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        string s;
        ll p;
        cin >> s >> p;
        ll n = s.size();
        if (n == 0) {
            cout << "1\n";
            continue;
        }
        ll inv10 = fpow(10, p-2, p);
        unordered_map<ll, ll> cnt, cnt1;
        cnt[0] = 1;
        cnt1[0] = 1;
        ll total = 1;
        ll h = 0;
        ll cur_inv = 1;
        ll ans = 0;

        for (int i = 0; i < n; i++) {
            ll d = s[i] - '0';
            cur_inv = (cur_inv * inv10) % p;
            h = (h + d * cur_inv) % p;
            // if (h < 0) h += p;

            ll dp1_cur = cnt[h];
            ll dp0_cur = (total - cnt1[h] + mod) % mod;

            if (i == n-1) {
                ans = (dp0_cur + dp1_cur) % mod;
            }

            cnt[h] = (cnt[h] + dp0_cur + dp1_cur) % mod;
            cnt1[h] = (cnt1[h] + dp1_cur) % mod;
            total = (total + dp1_cur) % mod;
        }

        cout << ans << '\n';
    }
    return 0;
}